package com.example.javamaday.leetcode;

import com.example.javamaday.leetcode.base.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeetCodeTest0236 {

    public static void main(String[] args) {

    }

    private Map<Integer, TreeNode> parent = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        // 记录p结点的父结点组合
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        // 从q结点开始，向上查找，找到其及其父节点存在于p结点父结点集合的Node，即为最近公共祖先
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

}
